/*
  Program: Mine Mayhem
  File:    solver.cc
  Date:    18 September to 16 December, 2006, version 2.90

  Grid and clue generation.
*/

/*
 * mines.c: Minesweeper clone with sophisticated grid generation.
 *	    From Simon Tatham's Puzzle collection.
 *
 * This is just the solver portion, adapted for use within my framework and
 * using some C++ (and reformatted to suit my style).
 * 
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NDEBUG
#include <assert.h>

#include <tws/message.h>

#include "minefld.h"
#include "board.h"
#include "options.h"

#include "tree234.h"
#include "puzzles.h"


//#define SOLVER_DIAGNOSTICS
//#define GENERATION_DIAGNOSTICS


// Create a modeless messagebox to allow cancelling grid generation.
class CancelBox : public MessageBox
{
public:
  CancelBox();
  ~CancelBox();
  bool Cancelled() { return retval; }
protected:
  BOOL DoEvents(const event* ev);
  bool pressed;
};


CancelBox::CancelBox()
: MessageBox("Generating", "Mine Mayhem", MB_CANCEL), pressed(false)
{
  Paint();
  RefreshWindow();
  CatchMouse();
  CatchKeys();
  retval = false;
}


CancelBox::~CancelBox()
{
  ReleaseKeys();
  ReleaseMouse();
}


BOOL CancelBox::DoEvents(const event* ev)
{
  if (ev->Type == W_NOTIFY && (ev->p1 == MB_CANCEL || ev->p1 == ID_SYSBOX))
  {
    if (ev->p2 == 1001) 	// button down
      pressed = true;
    else if (ev->p2 == 1000)	// button up
    {
      if (pressed)
	retval = true;
      return false;
    }
  }

  return MessageBox::DoEvents(ev);
}


/* ----------------------------------------------------------------------
 * Minesweeper solver, used to ensure the generated grids are
 * solvable without having to take risks.
 */

const int bit[3][3] = { { 0001, 0002, 0004 },
			{ 0010, 0020, 0040 },
			{ 0100, 0200, 0400 } };


/*
 * Count the bits in a word. Only needs to cope with 16 bits.
 */
static int bitcount16(int inword)
{
  unsigned int word = inword;

  word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
  word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
  word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
  word = ((word & 0xFF00) >> 8) + (word & 0x00FF);

  return (int)word;
}

/*
 * We use a tree234 to store a large number of small localised
 * sets, each with a mine count. We also keep some of those sets
 * linked together into a to-do list.
 */
struct set
{
  int x, y, mask, mines;
  int todo;
  struct set *prev, *next;
};

static int setcmp(void *av, void *bv)
{
  struct set *a = (struct set *)av;
  struct set *b = (struct set *)bv;

  int d = a->y - b->y;
  if (d == 0)
  {
    d = a->x - b->x;
    if (d == 0)
      d = a->mask - b->mask;
  }

  return d;
}


setstore::setstore() : todo_head(NULL), todo_tail(NULL), listsize(31)
{
  sets = newtree234(setcmp);
  list = snewn(listsize+1, struct set *);
}

void setstore::clear()
{
  struct set *s;
  while ((s = (struct set*)delpos234(sets, 0)) != NULL)
    sfree(s);
}

setstore::~setstore()
{
  clear();
  freetree234(sets);
  sfree(list);
}

/*
 * Take two input sets, in the form (x,y,mask). Munge the first by
 * taking either its intersection with the second or its difference
 * with the second. Return the new mask part of the first set.
 */
static int setmunge(int x1, int y1, int mask1,
		    int x2, int y2, int mask2, int diff)
{
  /*
   * Adjust the second set so that it has the same x,y
   * coordinates as the first.
   */
  int dx = field->cmpx(x2, x1),
      dy = field->cmpy(y2, y1);
  if (abs(dx) >= 3 || abs(dy) >= 3)
  {
    mask2 = 0;
  }
  else
  {
    for (; dx > 0; --dx)
    {
      mask2 &= ~0444;
      mask2 <<= 1;
      x2 = field->addx(x2, -1);
    }
    for (; dx < 0; ++dx)
    {
      mask2 &= ~0111;
      mask2 >>= 1;
      x2 = field->addx(x2, +1);
    }
    for (; dy > 0; --dy)
    {
      mask2 &= ~0700;
      mask2 <<= 3;
      y2 = field->addy(y2, -1);
    }
    for (; dy < 0; ++dy)
    {
      mask2 &= ~0007;
      mask2 >>= 3;
      y2 = field->addy(y2, +1);
    }
  }

  /*
   * Invert the second set if `diff' is set (we're after A &~ B
   * rather than A & B).
   */
  if (diff)
    mask2 ^= 0777;

  /*
   * Now all that's left is a logical AND.
   */
  return mask1 & mask2;
}

void setstore::add_todo(struct set *s)
{
  if (s->todo)
    return;			       /* already on it */

#ifdef SOLVER_DIAGNOSTICS
  printf("adding set on todo list: %d,%d %03o %d\n",
	 s->x, s->y, s->mask, s->mines);
#endif

  s->prev = todo_tail;
  if (s->prev)
    s->prev->next = s;
  else
    todo_head = s;
  todo_tail = s;
  s->next = NULL;
  s->todo = true;
}

void setstore::add(int x, int y, int mask, int mines)
{
  struct set *s;

  assert(mask != 0);

  /*
   * Normalise so that x and y are genuinely the bounding
   * rectangle.
   */
  while (!(mask & 0111))
    mask >>= 1, x = field->addx(x, +1);
  while (!(mask & 0007))
    mask >>= 3, y = field->addy(y, +1);

  /*
   * Create a set structure and add it to the tree.
   */
  s = snew(struct set);
  s->x = x;
  s->y = y;
  s->mask = mask;
  s->mines = mines;
  s->todo = false;
  if (add234(sets, s) != s)
  {
    /*
     * This set already existed! Free it and return.
     */
    sfree(s);
    return;
  }

  /*
   * We've added a new set to the tree, so put it on the todo list.
   */
  add_todo(s);
}

void setstore::remove(struct set *s)
{
  struct set *next = s->next, *prev = s->prev;

#ifdef SOLVER_DIAGNOSTICS
  printf("removing set %d,%d %03o\n", s->x, s->y, s->mask);
#endif

  /*
   * Remove s from the todo list.
   */
  if (prev)
    prev->next = next;
  else if (s == todo_head)
    todo_head = next;

  if (next)
    next->prev = prev;
  else if (s == todo_tail)
    todo_tail = prev;

  /*
   * Remove s from the tree.
   */
  del234(sets, s);

  /*
   * Destroy the actual set structure.
   */
  sfree(s);
}


/*
 * Return a list of all the sets which
 * overlap a provided input set.
 */
struct set **setstore::overlap(int x, int y, int mask)
{
  int nret = 0;
  struct set stmp, *s;
  int pos;
  int x2, y2;
  int wrap;

  /*
   * Find the first set with these top left coordinates.
   */
  stmp.x = x-2;
  stmp.y = y-2;
  stmp.mask = 0;

  /*
   * Find the right- and bottom-most coordinates.
   */
  x2 = x + ((mask & 0666) != 0) + ((mask & 0444) != 0);
  y2 = y + ((mask & 0770) != 0) + ((mask & 0700) != 0);

  wrap = false;
  if (field->canWrap())
  {
    wrap = (stmp.x < 0 || stmp.y < 0 || x2 >= field->cols || y2 >= field->rows);
    if (wrap)
    {
      if (stmp.x < 0 || x2 >= field->cols)
      {
	stmp.x = 0;
	x2 = field->cols - 1;
      }
      stmp.y = field->addy(stmp.y, 0);
      y2 = field->addy(y2, 1);
    }
  }

row:
  s = (struct set*)findrelpos234(sets, &stmp, NULL, REL234_GE, &pos);
  while (wrap || (s && s->y <= y2))
  {
    if (!wrap)
    {
      if (s->y != stmp.y)
      {
	stmp.y = s->y;
	if (s->x < x-2)
	  goto row;
      }
      if (s->x > x2)
      {
	if (s->y == y2)
	  break;
	stmp.y++;
	goto row;
      }
    }
    else
    {
      if (!s || s->y != stmp.y || s->x > x2)
      {
	stmp.y = field->addy(stmp.y, 1);
	if (stmp.y == y2)
	  break;
	goto row;
      }
    }

    /*
     * This set potentially overlaps the input one.
     * Compute the intersection to see if they really
     * overlap, and add it to the list if so.
     */
    if (setmunge(x, y, mask, s->x, s->y, s->mask, false))
    {
      /*
       * There's an overlap.
       */
      if (nret >= listsize)
      {
	listsize += 32;
	list = sresize(list, listsize+1, struct set *);
      }
      list[nret++] = s;
    }

    s = (struct set*)index234(sets, ++pos);
  }

  list[nret] = NULL;

  return list;
}

/*
 * Get an element from the head of the set todo list.
 */
struct set *setstore::todo()
{
  if (todo_head)
  {
    struct set *ret = todo_head;
    todo_head = ret->next;
    if (todo_head)
      todo_head->prev = NULL;
    else
      todo_tail = NULL;
    ret->next = ret->prev = NULL;
    ret->todo = false;
    return ret;
  }

  return NULL;
}

void squaretodo::add(Tile* t)
{
  if (head)
  {
    if (t->mines == 0)
    {
      t->next = head;
      head = t;
      return;
    }
    tail->next = t;
  }
  else
    head = t;
  tail = t;
  t->next = 0;
}

Tile* squaretodo::extract()
{
  Tile* t = head;
  if (head)
    head = head->next;

  return t;
}


void Minefield::Known(bool hint, int x, int y, int mask, int mine)
{
  int dx;

  for (;; y = addy(y, +1))
  {
    for (dx = 0; dx < 3; ++dx)
    {
      if (mask & 1)
      {
	Tile* t = grid[y][addx(x, dx)];
	/*
	 * It's possible that this square is _already_
	 * known, in which case we don't try to add it to
	 * the list twice.
	 */
	if (t->status == UNOPENED && t->hint == NONE)
	{
	  ++tileclues;
	  if (mine)
	    ++mineclues;
	  std.add(t);
	  if (hint)
	  {
	    t->hint = (mine) ? HINTMARK : HINTOPEN;
	    if (Hints > CLUES)
	      DisplayTile(t, (Hints == WHERE) ? HINT : t->hint);
	  }
	  else
	    t->status = (mine) ? MARKED : OPENED;
	}
	else if (t->status == MARKED && t->hint == HINTMARKU)
	{
	  t->hint = (mine) ? NONE : HINTMARKX;
	  if (Hints > CLUES)
	    DisplayTile(t, MARKED);
	  if (mine)
	  {
	    --minestogo;
	    std.add(t);
	  }
	  else
	    ++tileclues;
	}
      }
      mask >>= 1;
      if (mask == 0)
	return;
    }
  }
}


/*
 * This is data returned from the `perturb' function. It details
 * which squares have become mines and which have become clear. The
 * solver is (of course) expected to honourably not use that
 * knowledge directly, but to efficently adjust its internal data
 * structures and proceed based on only the information it
 * legitimately has.
 */
struct perturbation
{
  int x, y;
  int delta;			       /* +1 == become a mine; -1 == cleared */
};
struct perturbations
{
  int n;
  struct perturbation *changes;
};

/*
 * Main solver entry point. It fills in as much more of the
 * grid as it can.
 * 
 * Return value is (for generation):
 * 
 *  - -1 means deduction stalled and nothing could be done
 *  - 0 means deduction succeeded fully
 *  - >0 means deduction succeeded but some number of perturbation
 *    steps were required; the exact return value is the number of
 *    perturb calls.
 */

#if defined(SOLVER_DIAGNOSTICS)
/*
 * Dump the current known state of the grid.
 */
static char tile2chr(Tile* t)
{
  if (!t)
    return ' ';
  char ch;
  int s = t->status;
  int v = t->mines;
  if (s == UNOPENED)
    ch = (!t->hint) ? '?' : (t->hint == HINTMARK) ? 'm' : 'o';
  else if (s == MARKED)
    ch = (t->hint) ? '#' : (isMarks) ? v + '@' : '*';
  else if (v == 0)
    ch = '-';
  else
    ch = '0' + v;
  return ch;
}

static void print(int w, int h, Tile*** grid)
{
  int x, y;
  for (y = 0; y < h; y++)
  {
    for (x = 0; x < w; x++)
      putchar(tile2chr(grid[y][x]));
    putchar('\n');
  }
  fflush(stdout);
}
#endif

#ifdef GENERATION_DIAGNOSTICS
static void printgrid(int w, int h, Tile*** grid, Tile* starttile)
{
  int x, y;
  for (y = 0; y < h; y++)
  {
    for (x = 0; x < w; x++)
    {
      if (!grid[y][x])
      {
	putchar(' ');
	continue;
      }
      int v = grid[y][x]->mine;
      if (grid[y][x] == starttile && (Game == CROSS || Start != PERIMETER))
      {
	if (Game == CROSS || Start != NONE)
	{
	  assert(!v);
	  putchar('S');
	}
	else
	  putchar((v) ? 's' : 'S');
      }
      else
	putchar((v) ? '*' : '-');
    }
    putchar('\n');
  }
  putchar('\n');
}
#endif


void Minefield::CreateSet(int hint, int x, int y, int mask, int mines)
{
  int newmask, dx, dy, bit;

  /*
   * Compute the mask and mine count for this
   * set minus any newly known square(s).
   */
  newmask = 0;
  bit = 1;
  for (dy = y; /*dy < 3*/; dy = addy(dy, +1))
  {
    for (dx = 0; dx < 3; ++dx)
    {
      if (mask & 1)
      {
	Tile* t = grid[dy][addx(x, dx)];
#ifdef SOLVER_DIAGNOSTICS
	printf("grid %2d,%2d = %c\n", addx(x, dx), dy, tile2chr(t));
#endif
	if ((t->status == UNOPENED && t->hint == NONE) ||
	    (t->status == MARKED && t->hint == HINTMARKU))
	  newmask |= bit;
	else if ((t->status == MARKED && t->hint == NONE) ||
		 t->hint == HINTMARK)
	  mines--;
      }
      mask >>= 1;
      if (mask == 0)
	goto Break;
      bit <<= 1;
    }
  }
  Break:

  /*
   * Insert the new set into the collection,
   * unless it's been whittled right down to
   * nothing.
   */
  if (newmask)
  {
    /*
     * If this set has a mine count of zero or
     * of its own cardinality, we can immediately
     * mark all the squares in the set as known.
     */
    if (mines == 0 || mines == bitcount16(newmask))
    {
#ifdef SOLVER_DIAGNOSTICS
      printf("easy: %d,%d %03o %c\n", x, y, newmask, mines ? 'm' : 'o');
#endif
      Known(hint, x, y, newmask, mines);
    }
    else
      ss.add(x, y, newmask, mines);
  }
}


static DWORD ticks;
static bool  cancelled;
static CancelBox* mb;


int Minefield::Solve(int* mineset, int minecnt)
{
  struct set **list;
  int  x, y, i, j;
  int  nperturbs;
  bool hint = (minecnt == 0);

  nperturbs = (hint) ? tileclues : 0;

  /*
   * Main deductive loop.
   */
  while (1)
  {
    int done_something = false;
    struct set *s;
    Tile* t;

    /*
     * If there are any known squares on the todo list, process
     * them and construct a set for each.
     */
    while ((t = std.extract()))
    {
      x = t->grid.x;
      y = t->grid.y;

#ifdef SOLVER_DIAGNOSTICS
      printf("known square at %d,%d [%c]\n", x, y, tile2chr(t));
#endif

      /*
       * Now, whether the square is empty or full, we must
       * find any set which contains it and replace it with
       * one which does not.
       */
#ifdef SOLVER_DIAGNOSTICS
      printf("finding sets containing this square\n");
#endif
      list = ss.overlap(x, y, 1);

      for (j = 0; list[j]; j++)
      {
	s = list[j];
	CreateSet(hint, s->x, s->y, s->mask, s->mines);

	/*
	 * Destroy the old one; it is actually obsolete.
	 */
	ss.remove(s);
      }

      if (t->status == OPENED ||
	  (isMarks && t->status == MARKED && t->hint == NONE))
      {
#ifdef SOLVER_DIAGNOSTICS
	printf("creating set around known square %d,%d\n", x, y);
#endif
	CreateSet(hint, addx(x, -1), addy(y, -1), t->mask, t->mines);
      }
    }

    /*
     * Now pick a set off the to-do list and attempt deductions
     * based on it.
     */
    if ((s = ss.todo()) != NULL)
    {
#ifdef SOLVER_DIAGNOSTICS
      printf("set to do: %d,%d %03o %d\n", s->x, s->y, s->mask, s->mines);
#endif
      /*
       * Firstly, see if this set has a mine count of zero or
       * of its own cardinality (only needed if perturbed).
       */
      if (s->mines == 0 || s->mines == bitcount16(s->mask))
      {
	/*
	 * If so, we can immediately mark all the squares
	 * in the set as known.
	 */
#ifdef SOLVER_DIAGNOSTICS
	printf("easy (%c)\n", s->mines ? 'm' : 'o');
#endif
	Known(hint, s->x, s->y, s->mask, s->mines);

	/*
	 * Having done that, we need do nothing further
	 * with this set; marking all the squares in it as
	 * known will eventually eliminate it, and will
	 * also permit further deductions about anything
	 * that overlaps it.
	 */
	ss.remove(s);
	continue;
      }

      /*
       * Search through all the sets which overlap this one.
       */
      list = ss.overlap(s->x, s->y, s->mask);

      for (j = 0; list[j]; j++)
      {
    	struct set *s2 = list[j];
	int swing, s2wing, swc, s2wc, swm, s2wm;

	if (s2 == s)
	  continue;

    	/*
    	 * Find the non-overlapping parts s2-s and s-s2,
    	 * and their cardinalities.
    	 * 
    	 * I'm going to refer to these parts as `wings'
    	 * surrounding the central part common to both
    	 * sets. The `s wing' is s-s2; the `s2 wing' is
    	 * s2-s.
    	 */
	swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask, true);
	s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask, true);
    	swc = bitcount16(swing);
    	s2wc = bitcount16(s2wing);
	swm = s->mines - s2->mines;
	s2wm = s2->mines - s->mines;

    	/*
    	 * If one set has more mines than the other, and
    	 * the number of extra mines is equal to the
    	 * cardinality of that set's wing, then we can mark
    	 * every square in the wing as a known mine, and
    	 * every square in the other wing as known clear.
    	 */
	if (swc == swm || s2wc == s2wm)
	{
#ifdef SOLVER_DIAGNOSTICS
	  printf("medium: %d,%d %03o %c; %d,%d %03o %c\n",
		 s->x, s->y, swing, swc == swm ? 'm' : 'o',
		 s2->x, s2->y, s2wing, s2wc == s2wm ? 'm' : 'o');
#endif
	  Known(hint, s->x, s->y, swing, (swc == swm));
	  Known(hint, s2->x, s2->y, s2wing, (s2wc == s2wm));
	  continue;
    	}

    	/*
    	 * Failing that, see if one set is a subset of the
    	 * other. If so, we can divide up the mine count of
    	 * the larger set between the smaller set and its
    	 * complement, even if neither smaller set ends up
    	 * being immediately clearable.
    	 */
	if (swc == 0 && s2wc != 0)
	{
	  /* s is a subset of s2. */
	  assert(s2->mines > s->mines);
#ifdef SOLVER_DIAGNOSTICS
	  printf("hard...\n");
#endif
	  ss.add(s2->x, s2->y, s2wing, s2wm);
	}
	else if (s2wc == 0 && swc != 0)
	{
	  /* s2 is a subset of s. */
	  assert(s->mines > s2->mines);
#ifdef SOLVER_DIAGNOSTICS
	  printf("hard...\n");
#endif
	  ss.add(s->x, s->y, swing, swm);
	}
      }

      /*
       * In this situation we have definitely done
       * _something_, even if it's only reducing the size of
       * our to-do list.
       */
      continue;
    }

    if (Game == CROSS && field[tile_count-1].status == UNOPENED
		      && field[tile_count-1].hint == NONE)
    {
      /*
       * Since it's known the end tile is blank, see if
       * any opened tiles border its neighbours.
       */
      Tile* t = &field[tile_count-1];
      around (t, t1)
      {
	if ((*t1)->status == OPENED)
	{
	  Known(hint, t->grid.x, t->grid.y, 1, false);
	  done_something = true;
	}
	else if ((*t1)->status == UNOPENED && (*t1)->hint == NONE)
	{
	  around (*t1, t2)
	  {
	    if ((*t2)->status == OPENED)
	    {
	      Known(hint, (*t1)->grid.x, (*t1)->grid.y, 1, false);
	      done_something = true;
	      break;
	    }
	  }
	}
      }
      if (done_something)
	continue;
    }

    /*
     * We have nothing left on our todo list, which means
     * all localised deductions have failed. Our next step
     * is to resort to global deduction based on the total
     * mine count. This is computationally expensive
     * compared to any of the above deductions, which is
     * why we only ever do it when all else fails, so that
     * hopefully it won't have to happen too often.
     */

    int minesleft, squaresleft;
    int nsets, setused[10], cursor;

    /*
     * Start by scanning the current grid state to work out
     * how many unknown squares we still have, and how many
     * mines are to be placed in them.
     */
    squaresleft = spaces + minestogo - tileclues;
    minesleft = minestogo - mineclues;

#ifdef SOLVER_DIAGNOSTICS
    printf("global deduction time: squaresleft=%d minesleft=%d\n",
	   squaresleft, minesleft);
    print(layout.dim.x, layout.dim.y, grid);
#endif

    /*
     * If there _are_ no unknown squares, we have actually
     * finished.
     */
    if (squaresleft == 0)
    {
      assert(minesleft == 0);
      break;
    }

    if (mb)
    {
      ws.CheckForEvents();
      if (mb->Cancelled())
      {
	cancelled = true;
	return -1;
      }
    }
    else if (!hint && GetTicks() - ticks >= 5000)
      mb = new CancelBox();

    /*
     * These deductions don't necessarily lead to a field
     * that can actually be crossed.
     */
    if (Game == CLEAR)
    {
      /*
       * First really simple case: if there are no more mines
       * left, or if there are exactly as many mines left as
       * squares to play them in, then it's all easy.
       */
      if (minesleft == 0 || minesleft == squaresleft)
      {
	foralltiles
	{
	  Tile* t = &field[tile];
	  if ((t->status == UNOPENED && t->hint == NONE) ||
	      (t->status == MARKED && t->hint == HINTMARKU))
	    Known(hint, t->grid.x, t->grid.y, 1, minesleft);
	}
	continue;	/* now go back to main deductive loop */
      }

      /*
       * Failing that, we have to do some _real_ work.
       * Ideally what we do here is to try every single
       * combination of the currently available sets, in an
       * attempt to find a disjoint union (i.e. a set of
       * squares with a known mine count between them) such
       * that the remaining unknown squares _not_ contained
       * in that union either contain no mines or are all
       * mines.
       *
       * Actually enumerating all 2^n possibilities will get
       * a bit slow for large n, so I artificially cap this
       * recursion at n=10 to avoid too much pain.
       */
      nsets = count234(ss.sets);
      if (nsets > 0 && nsets <= (int)lenof(setused))
      {
	/*
	 * Doing this with actual recursive function calls
	 * would get fiddly because a load of local
	 * variables from this function would have to be
	 * passed down through the recursion. So instead
	 * I'm going to use a virtual recursion within this
	 * function. The way this works is:
	 *
	 *  - we have an array `setused', such that
	 *    setused[n] is 0 or 1 depending on whether set
	 *    n is currently in the union we are
	 *    considering.
	 *
	 *  - we have a value `cursor' which indicates how
	 *    much of `setused' we have so far filled in.
	 *    It's conceptually the recursion depth.
	 *
	 * We begin by setting `cursor' to zero. Then:
	 *
	 *  - if cursor can advance, we advance it by one.
	 *    We set the value in `setused' that it went
	 *    past to 1 if that set is disjoint from
	 *    anything else currently in `setused', or to 0
	 *    otherwise.
	 *
	 *  - If cursor cannot advance because it has
	 *    reached the end of the setused list, then we
	 *    have a maximal disjoint union. Check to see
	 *    whether its mine count has any useful
	 *    properties. If so, mark all the squares not
	 *    in the union as known and terminate.
	 *
	 *  - If cursor has reached the end of setused and
	 *    the algorithm _hasn't_ terminated, back
	 *    cursor up to the nearest 1, turn it into a 0
	 *    and advance cursor just past it.
	 *
	 *  - If we attempt to back up to the nearest 1 and
	 *    there isn't one at all, then we have gone
	 *    through all disjoint unions of sets in the
	 *    list and none of them has been helpful, so we
	 *    give up.
	 *
	 * jmh: Before trying this see if the sets actually
	 *	have enough information to succeed.
	 */
	struct set *sets[lenof(setused)];
	int setsquares, setmines, newmask;
	sets[0] = (struct set*)index234(ss.sets, 0);
	setsquares = bitcount16(sets[0]->mask);
	setmines = sets[0]->mines;
	for (i = 1; i < nsets; i++)
	{
	  sets[i] = (struct set*)index234(ss.sets, i);
	  /*
	   * Approximate the number of unique set squares by
	   * taking the difference with the previous set - this
	   * eliminates most side-by-side overlaps, but probably
	   * not many vertical ones. If any overlap did occur,
	   * reduce the mine count of that set by one.
	   */
	  newmask = setmunge(sets[i]->x, sets[i]->y, sets[i]->mask,
			     sets[i-1]->x, sets[i-1]->y, sets[i-1]->mask, true);
	  setsquares += bitcount16(newmask);
	  setmines += sets[i]->mines - (newmask != sets[i]->mask);
	}
#ifdef SOLVER_DIAGNOSTICS
	printf("remaining sets approx: squaresleft=%d minesleft=%d\n",
	       setsquares, setmines);
#endif

	cursor = 0;
	if (setmines >= minesleft || squaresleft - setsquares <= minesleft)
	while (1)
	{
	  if (cursor < nsets)
	  {
	    int ok = true;

	    /* See if any existing set overlaps this one. */
	    for (i = 0; i < cursor; i++)
	    {
	      if (setused[i] &&
		  setmunge(sets[cursor]->x, sets[cursor]->y, sets[cursor]->mask,
			   sets[i]->x, sets[i]->y, sets[i]->mask, false))
	      {
		ok = false;
		break;
	      }
	    }
	    if (ok)
	    {
	      /*
	       * We're adding this set to our union,
	       * so adjust minesleft and squaresleft
	       * appropriately.
	       */
	      minesleft -= sets[cursor]->mines;
	      squaresleft -= bitcount16(sets[cursor]->mask);
	    }

	    setused[cursor++] = ok;
	  }
	  else
	  {
#ifdef SOLVER_DIAGNOSTICS
	    printf("trying a set combination with %d %d\n",
		   squaresleft, minesleft);
#endif /* SOLVER_DIAGNOSTICS */

	    /*
	     * We've reached the end. See if we've got
	     * anything interesting.
	     */
	    if (squaresleft > 0 && (minesleft == 0 || minesleft == squaresleft))
	    {
	      /*
	       * We have! There is at least one
	       * square not contained within the set
	       * union we've just found, and we can
	       * deduce that either all such squares
	       * are mines or all are not (depending
	       * on whether minesleft==0). So now all
	       * we have to do is actually go through
	       * the grid, find those squares, and
	       * mark them.
	       */
	      foralltiles
	      {
		Tile* t = &field[tile];
		if ((t->status == UNOPENED && t->hint == NONE) ||
		    (t->status == MARKED && t->hint == HINTMARKU))
		{
		  int outside = true;
		  x = t->grid.x;
		  y = t->grid.y;
		  for (j = 0; j < nsets; j++)
		  {
		    if (setused[j] &&
			setmunge(sets[j]->x, sets[j]->y, sets[j]->mask,
				 x, y, 1, false))
		    {
		      outside = false;
		      break;
		    }
		  }
		  if (outside)
		    Known(hint, x, y, 1, minesleft);
		}
	      }
	      done_something = true;
	      break;	   /* return to main deductive loop */
	    }

	    /*
	     * If we reach here, then this union hasn't
	     * done us any good, so move on to the
	     * next. Backtrack cursor to the nearest 1,
	     * change it to a 0 and continue.
	     */
	    while (--cursor >= 0 && !setused[cursor]) ;
	    if (cursor >= 0)
	    {
	      assert(setused[cursor]);

	      /*
	       * We're removing this set from our
	       * union, so re-increment minesleft and
	       * squaresleft.
	       */
	      minesleft += sets[cursor]->mines;
	      squaresleft += bitcount16(sets[cursor]->mask);

	      setused[cursor++] = 0;
	    }
	    else
	    {
	      /*
	       * We've backtracked all the way to the
	       * start without finding a single 1,
	       * which means that our virtual
	       * recursion is complete and nothing
	       * helped.
	       */
	      break;
	    }
	  }
	}
      }
      if (done_something)
	continue;

#ifdef SOLVER_DIAGNOSTICS
      /*
       * Dump the current known state of the grid.
       */
      printf("solver ran out of steam, ret=%d, grid:\n",
	     (hint) ? tileclues - nperturbs : nperturbs);
      print(layout.dim.x, layout.dim.y, grid);

      {
	struct set *s;

	for (i = 0; (s = (struct set*)index234(ss.sets, i)) != NULL; i++)
	  printf("remaining set: %d,%d %03o %d\n", s->x, s->y, s->mask, s->mines);
      }
#endif
    }

    /*
     * Now we really are at our wits' end as far as solving
     * this grid goes. Our only remaining option is to call
     * a perturb function and ask it to modify the grid to
     * make it easier.
     */
    if (!hint)
    {
      struct perturbations *ret;
      struct set *s;

      /*
       * Whilst it would be nice to completely solve the cross
       * game, it is not necessary, so see if it's good enough.
       */
      if (Game == CROSS && field[tile_count-1].status == OPENED)
      {
#ifdef SOLVER_DIAGNOSTICS
	printf("good enough for crossing\n");
#endif
	break;
      }

      nperturbs++;

      /*
       * Choose a set at random from the current selection,
       * and ask the perturb function to either fill or empty
       * it.
       * 
       * If we have no sets at all, we must give up.
       */
      if (count234(ss.sets) == 0)
      {
#ifdef SOLVER_DIAGNOSTICS
    	printf("perturbing on entire unknown set\n");
#endif
	ret = Perturb(0, 0, 0, mineset, minecnt);
      }
      else
      {
	s = (struct set*)index234(ss.sets, random_upto(count234(ss.sets)));
#ifdef SOLVER_DIAGNOSTICS
    	printf("perturbing on set %d,%d %03o\n", s->x, s->y, s->mask);
#endif
	ret = Perturb(s->x, s->y, s->mask, mineset, minecnt);
      }

      if (ret)
      {
	assert(ret->n > 0);    /* otherwise should have been NULL */

    	/*
    	 * A number of squares have been fiddled with, and
    	 * the returned structure tells us which. Adjust
    	 * the mine count in any set which overlaps one of
    	 * those squares, and put them back on the to-do
    	 * list. Also, if the square itself is marked as a
    	 * known non-mine, put it back on the squares-to-do
    	 * list.
    	 */
	for (i = 0; i < ret->n; i++)
	{
#ifdef SOLVER_DIAGNOSTICS
	  printf("perturbation %s mine at %d,%d\n",
		 ret->changes[i].delta > 0 ? "added" : "removed",
		 ret->changes[i].x, ret->changes[i].y);
#endif

	  if (ret->changes[i].delta < 0 &&
	      grid[ret->changes[i].y][ret->changes[i].x]->status != UNOPENED)
	  {
	    std.add(grid[ret->changes[i].y][ret->changes[i].x]);
	  }

	  list = ss.overlap(ret->changes[i].x, ret->changes[i].y, 1);

	  for (j = 0; list[j]; j++)
	  {
	    list[j]->mines += ret->changes[i].delta;
	    ss.add_todo(list[j]);
	  }
    	}

    	/*
    	 * Now free the returned data.
    	 */
    	sfree(ret->changes);
    	sfree(ret);

#ifdef SOLVER_DIAGNOSTICS
    	/*
    	 * Dump the current known state of the grid.
    	 */
    	printf("state after perturbation:\n");
    	print(layout.dim.x, layout.dim.y, grid);

    	{
	  struct set *s;

	  for (i = 0; (s = (struct set*)index234(ss.sets, i)) != NULL; i++)
	    printf("remaining set: %d,%d %03o %d\n",
		   s->x, s->y, s->mask, s->mines);
    	}
#endif

    	/*
    	 * And now we can go back round the deductive loop.
    	 */
    	continue;
      }

      nperturbs = -1;		/* failed to complete */
    }

    /*
     * If we get here, even that didn't work (either we didn't
     * have a perturb function or it returned failure), so we
     * give up entirely.
     */
    break;
  }

  return (hint) ? tileclues - nperturbs : nperturbs;
}


/* Structure used internally to mineperturb(). */
struct square
{
  int x, y, type, random;
};

static int squarecmp(const void *av, const void *bv)
{
  const struct square *a = (const struct square *)av;
  const struct square *b = (const struct square *)bv;

  int d = a->type - b->type;
  if (d == 0)
    d = a->random - b->random;

  return d;
}

/*
 * Normally this function is passed an (x,y,mask) set description.
 * On occasions, though, there is no _localised_ set being used,
 * and the set being perturbed is supposed to be the entirety of
 * the unreachable area. This is signified by the special case
 * mask==0: in this case, anything labelled UNOPENED in the grid
 * is part of the set.
 * 
 * Allowing perturbation in this special case appears to make it
 * guaranteeably possible to generate a workable grid for any mine
 * density, but they tend to be a bit boring, with mines packed
 * densely into far corners of the grid and the remainder being
 * less dense than one might like. Therefore, to improve overall
 * grid quality I disable this feature for the first few attempts,
 * and fall back to it after no useful grid has been generated.
 *
 * jmh: I take a different approach if mask==0. When this occurs
 * there are unopened regions entirely surrounded by mines. Find an
 * empty square in each region and swap it with a mine that borders
 * it. This will create a new set and end up generating a more
 * interesting grid than the above method.
 */
struct perturbations* Minefield::Perturb(int setx, int sety, int mask,
					 int* mineset, int minecnt)
{
  struct square *sqlist;
  int x, y, dx, dy, i, n, nfull, nempty;
  struct square *tofill[9], *toempty[9], **todo;
  int ntofill, ntoempty, ntodo, dtodo, dset;
  struct perturbations *ret;
  Tile* setlist[minecnt];

  if (mask == 0)
  {
    int sets[10];
    bool seen[rows][cols];
    memset(seen, true, sizeof(seen));
    for (i = 0; i < minecnt; ++i)
      seen[field[mineset[i]].grid.y][field[mineset[i]].grid.x] = false;

    /*
     * Find up to ten unopened regions.
     */
    ntodo = nfull = nempty = ntofill = ntoempty = 0;
    for (i = 0; i < minecnt; ++i)
    {
      Tile* t = &field[mineset[i]];
      if (t->status == UNOPENED && !seen[t->grid.y][t->grid.x])
      {
	seen[t->grid.y][t->grid.x] = true;
	do
	{
	  if (!t->mine)
	    setlist[ntofill + nempty++] = t;
	  around (t, t1)
	  {
	    if (!seen[(*t1)->grid.y][(*t1)->grid.x])
	    {
	      seen[(*t1)->grid.y][(*t1)->grid.x] = true;
	      if ((*t1)->status == MARKED)
		setlist[minecnt - (ntoempty + ++nfull)] = *t1;
	      else if ((*t1)->status == UNOPENED)
		std.add(*t1);
	    }
	  }
	} while ((t = std.extract()));
	sets[ntodo] = nempty | (nfull << 16);
	if (++ntodo == lenof(sets))
	  break;
	ntofill += nempty;
	ntoempty += nfull;
	nempty = nfull = 0;
      }
    }
    if (ntofill == 0)
    {
      /*
       * There are no empty squares in the unopened regions
       * (so it's the cross game). Pick a random blank square
       * from the field and swap it with a random boundary mine.
       * If there are no blanks, give up.
       */
      for (i = 0; i < minecnt; ++i)
      {
	Tile* t = &field[mineset[i]];
	if (t->mines == 0)
	  setlist[ntofill++] = t;
	if (ntoempty == 0 && t->mine)
	{
	  /*
	   * Need to find the boundary mines around the last region.
	   */
	  around (t, t1)
	    if ((*t1)->status == UNOPENED)
	    {
	      setlist[minecnt - ++nfull] = t;
	      break;
	    }
	}
      }
      if (ntofill == 0)
	return NULL;
      ntodo = 1;
      sets[0] = ntofill | ((ntoempty ? ntoempty : nfull) << 16);
    }
    /*
     * Now pick a random empty square from each set
     * and swap it with a random mine from its boundary.
     */
    ret = snew(struct perturbations);
    ret->n = 2 * ntodo;
    ret->changes = snewn(ret->n, struct perturbation);
    i = ntofill = ntoempty = 0;
    for (int j = 0; j < ntodo; ++j)
    {
      nempty = sets[j] & 0xFFFF;
      nfull = sets[j] >> 16;
      if (nempty != 0)
      {
	n = ntofill + random_upto(nempty);
	ret->changes[i].x = setlist[n]->grid.x;
	ret->changes[i].y = setlist[n]->grid.y;
	ret->changes[i].delta = +1;
	++i;
	n = minecnt-1 - (ntoempty + random_upto(nfull));
	ret->changes[i].x = setlist[n]->grid.x;
	ret->changes[i].y = setlist[n]->grid.y;
	ret->changes[i].delta = -1;
	++i;
      }
      ntofill += nempty;
      ntoempty += nfull;
    }
    ret->n = i;
  }
  else
  {
    /*
     * Make a list of all the squares in the grid which we can
     * possibly use. This list should be in preference order, which
     * means
     *
     *	- first, unknown squares on the boundary of known space
     *	- next, unknown squares beyond that boundary
     *	- as a very last resort, known squares, but not within one
     *	square of the starting position.
     *
     * Each of these sections needs to be shuffled independently.
     * We do this by preparing list of all squares and then sorting
     * it with a random secondary key.
     */
    sqlist = snewn(minecnt, struct square);
    n = 0;
    for (i = 0; i < minecnt; ++i)
    {
      Tile* t = &field[mineset[i]];
      x = t->grid.x;
      y = t->grid.y;

      /*
       * If this square is in the input set, don't put
       * it on the list!
       */
      dx = cmpx(x, setx);
      dy = cmpy(y, sety);
      if (dx >= 0 && dx < 3 &&
	  dy >= 0 && dy < 3 &&
	  (mask & bit[dy][dx]))
	continue;

      sqlist[n].x = x;
      sqlist[n].y = y;

      if (t->status != UNOPENED)
      {
	sqlist[n].type = 3;	  /* known square */
      }
      else
      {
	/*
	 * Unknown square. Examine everything around it and
	 * see if it borders on any known squares. If it
	 * does, it's class 1, otherwise it's 2.
	 */

	sqlist[n].type = 2;

	around (t, t1)
	{
	  if ((*t1)->status != UNOPENED)
	  {
	    sqlist[n].type = 1;
	    break;
	  }
	}
      }

      /*
       * Finally, a random number to cause qsort to
       * shuffle within each group.
       */
      sqlist[n].random = random_upto(0x80000000u);

      n++;
    }

    qsort(sqlist, n, sizeof(struct square), squarecmp);

    /*
     * Now count up the number of full and empty squares in the set
     * we've been provided.
     */
    nfull = nempty = 0;
    for (dy = 0; dy < 3; dy++)
      for (dx = 0; dx < 3; dx++)
	if (mask & bit[dy][dx])
	{
	  if (grid[addy(sety,dy)][addx(setx,dx)]->mine)
	    nfull++;
	  else
	    nempty++;
	}

    /*
     * Now go through our sorted list until we find either `nfull'
     * empty squares, or `nempty' full squares; these will be
     * swapped with the appropriate squares in the set to either
     * fill or empty the set while keeping the same number of mines
     * overall.
     */
    ntofill = ntoempty = 0;
    for (i = 0; i < n; i++)
    {
      struct square *sq = &sqlist[i];
      if (grid[sq->y][sq->x]->mine)
	toempty[ntoempty++] = sq;
      else
	tofill[ntofill++] = sq;
      if (ntofill == nfull || ntoempty == nempty)
	break;
    }

    /*
     * If we haven't found enough empty squares outside the set to
     * empty it into _or_ enough full squares outside it to fill it
     * up with, we'll have to settle for doing only a partial job.
     * In this case we choose to always _fill_ the set (because
     * this case will tend to crop up when we're working with very
     * high mine densities and the only way to get a solvable grid
     * is going to be to pack most of the mines solidly around the
     * edges). So now our job is to make a list of the empty
     * squares in the set, and shuffle that list so that we fill a
     * random selection of them.
     */
    if (ntofill != nfull && ntoempty != nempty)
    {
      int k;

      assert(ntoempty != 0);

      i = 0;
      for (dy = 0; dy < 3; dy++)
	for (dx = 0; dx < 3; dx++)
	  if (mask & bit[dy][dx])
	  {
	    if (!grid[addy(sety,dy)][addx(setx,dx)]->mine)
	      setlist[i++] = grid[addy(sety,dy)][addx(setx,dx)];
	  }
      assert(i > ntoempty);
      /*
       * Now pick `ntoempty' items at random from the list.
       */
      for (k = 0; k < ntoempty; k++)
      {
	int index = k + random_upto(i - k);
	Tile* tmp;

	tmp = setlist[k];
	setlist[k] = setlist[index];
	setlist[index] = tmp;
      }
    }
    else
      *setlist = NULL;

    /*
     * Now we're pretty much there. We need to either
     *	(a) put a mine in each of the empty squares in the set, and
     *	    take one out of each square in `toempty'
     *	(b) take a mine out of each of the full squares in the set,
     *	    and put one in each square in `tofill'
     * depending on which one we've found enough squares to do.
     *
     * So we start by constructing our list of changes to return to
     * the solver, so that it can update its data structures
     * efficiently rather than having to rescan the whole grid.
     */
    ret = snew(struct perturbations);
    if (ntofill == nfull)
    {
      todo = tofill;
      ntodo = ntofill;
      dtodo = +1;
      dset = -1;
    }
    else
    {
      /*
       * (We also fall into this case if we've constructed a
       * setlist.)
       */
      todo = toempty;
      ntodo = ntoempty;
      dtodo = -1;
      dset = +1;
    }
    ret->n = 2 * ntodo;
    ret->changes = snewn(ret->n, struct perturbation);
    for (i = 0; i < ntodo; i++)
    {
      ret->changes[i].x = todo[i]->x;
      ret->changes[i].y = todo[i]->y;
      ret->changes[i].delta = dtodo;
    }
    /* now i == ntodo */
    if (*setlist)
    {
      int j;
      assert(todo == toempty);
      for (j = 0; j < ntoempty; j++)
      {
	ret->changes[i].x = setlist[j]->grid.x;
	ret->changes[i].y = setlist[j]->grid.y;
	ret->changes[i].delta = dset;
	i++;
      }
    }
    else
    {
      for (dy = 0; dy < 3; dy++)
	for (dx = 0; dx < 3; dx++)
	  if (mask & bit[dy][dx])
	  {
	    int xx = addx(setx,dx);
	    int yy = addy(sety,dy);
	    int currval = (grid[yy][xx]->mine ? +1 : -1);
	    if (dset == -currval)
	    {
	      ret->changes[i].x = xx;
	      ret->changes[i].y = yy;
	      ret->changes[i].delta = dset;
	      i++;
	    }
	  }
    }
    assert(i == ret->n);

    sfree(sqlist);
  }

  /*
   * Having set up the precise list of changes we're going to
   * make, we now simply make them and return.
   */
  for (i = 0; i < ret->n; i++)
  {
    int delta;

    x = ret->changes[i].x;
    y = ret->changes[i].y;
    delta = ret->changes[i].delta;
    Tile* t = grid[y][x];

    /*
     * Check we're not trying to add an existing mine or remove
     * an absent one.
     */
    assert((delta < 0) ^ (t->mine == 0));

    /*
     * Actually make the change.
     */
    t->mine = (delta > 0);
    MineCount(t, delta);
    if (t->status != UNOPENED)
      t->status = (delta > 0) ? (++mineclues, MARKED) : (--mineclues, OPENED);
  }

#ifdef GENERATION_DIAGNOSTICS
  printf("grid after perturbing:\n");
  printgrid(layout.dim.x, layout.dim.y, grid, starttile);
#endif

  return ret;
}


bool Minefield::Generate(int* mineset, int minecnt)
{
  int success;

  cancelled = false;
  mb = 0;
  ticks = GetTicks();

  do
  {
    success = false;

    foralltiles
    {
      field[tile].mine  =
      field[tile].mines = 0;
    }

    int cnt = minecnt;
    for (int m = layout.mines; --m >= 0;)
    {
      int pos = random_upto(cnt--);
      int t = mineset[pos];
      field[t].mine = 1;
      MineCount(&field[t], 1);
      mineset[pos] = mineset[cnt];
      mineset[cnt] = t;
    }

#ifdef GENERATION_DIAGNOSTICS
    printf("grid after initial generation:\n");
    printgrid(layout.dim.x, layout.dim.y, grid, starttile);
#endif

    /*
     * Should only need to run the solver twice - once to tweak the
     * mine positions and then again to verify those positions.
     *
     * We bypass this bit if we're not after a unique grid.
     */
    if (Game == CROSS || (isLogical && (Start == BLANK || Start == PERIMETER)))
    {
      int solveret;
      do
      {
	if (Game == CLEAR && Start == PERIMETER)
	{
	  for (int* tile = perimeter; *tile >= 0; ++tile)
	  {
	    field[*tile].status = OPENED;
	    std.add(&field[*tile]);
	    ++tileclues;
	  }
	}
	else
	{
	  starttile->status = OPENED;
	  std.add(starttile);
	  ++tileclues;
	}

	solveret = Solve(mineset, minecnt);

	foralltiles
	  field[tile].status = UNOPENED;
	tileclues = mineclues = 0;
	ss.clear();

      } while (solveret > 0);

      if (cancelled)
	break;
      success = (solveret == 0);
    }
    else
    {
      success = true;
    }

  } while (!success);

  delete mb;

  return !cancelled;
}


void Minefield::Solve()
{
  Solve(NULL, 0);

  if (Hints)
    Board->DisplayClues(tileclues);
}


void Minefield::ShowHints()
{
  foralltiles
  {
    if (field[tile].hint)
    {
      int v;
      if (Hints <= CLUES)
      {
	if (!isFinished)
	  v = (field[tile].status == MARKED) ? MARKED : UNOPENED;
	else if (isFinished == LOST)
	{
	  if (field[tile].mine)
	    v = (field[tile].status == MARKED) ? MARKED : MINE;
	  else
	    v = (field[tile].status == MARKED) ? WRONGMINE : UNOPENED;
	}
	else if (Hints == NONE && Game == CLEAR)
	  v = (field[tile].mine) ? MARKED : field[tile].mines;
	else
	  v = UNOPENED;
      }
      else
      {
	v = (field[tile].status == MARKED) ? MARKED :
	    (Hints == WHERE) ? HINT : field[tile].hint;
      }
      DisplayTile(&field[tile], v);
    }
    else if (field[tile].status == UNOPENED &&
	     isFinished == WON && Game == CLEAR)
    {
      DisplayTile(&field[tile], (Hints) ? UNOPENED :
				(field[tile].mine) ? MARKED :
				field[tile].mines);
    }
  }
  Board->DisplayClues((Hints == NONE) ? -1 : tileclues);
  if (Game == CLEAR && isFinished == WON)
    Board->DisplayProgress(Hints == NONE ? 0 : mines,
			   Hints == NONE ? 0 : spaces);
}
